import java.util.ArrayList;

public class Solution {
    //滑动窗口的最大值
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> arr=new ArrayList<>();
        if(size>num.length||num.length==0||size<=0){
            return new ArrayList<Integer>();
        }
        for(int i=0;i<=num.length-size;i++){
            int max=num[i];
            for(int j=i+1;j<i+size;j++){
                if(max<num[j]){
                    max=num[j];
                }
            }
            arr.add(max);
        }
        return arr;
    }
    //剪绳子
    public int cutRope(int target) {
        if(target<=3){
            return target-1;
        }
        //找一个记录绳子分的最大值
        int [] dp=new int [target+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        dp[4]=4;
        for(int i=5;i<=target;i++){
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],dp[i-j]*j);
            }
        }
        return dp[target];
    }
    //重建二叉树
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    //方法一
    public int preIndex=0;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        return child(pre,vin,0,vin.length-1);
    }
    public TreeNode child(int [] pre ,int[] vin,int start,int end){
        if(start>end){
            return null;
        }
        int ret=pre[preIndex];
        int index=findIndex(vin,start,end,ret);
        if(index==-1){
            return null;
        }
        preIndex++;
        TreeNode root=new TreeNode(ret);
        root.left=child(pre,vin,start,index-1);
        root.right=child(pre,vin,index+1,end);
        return root;
    }
    public int findIndex(int [] vin ,int start,int end,int ret){
        for(int i=start;i<=end;i++){
           if(vin[i]==ret){
              return i;
           }
        }
        return -1;
    }
}